package conclusion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Permutation:
 * 
 * No repetition:
 * When we choose k objects out of n-element set
 * in such a way that order matters and each object
 * can only be chosen once: n! / (n-k)! = n(n-1)(n-2)...(n-k+1)
 * 
 * With repetition:
 * 1. When we choose k objects from n-element set when order is 
 *   important and one object can be chosen more than once: n^k
 * 
 * 2. The number of different permutations of n objects,
 *   where there are n1 indistinguishable objects of type 1,
 *   n2 indistinguishable objects of type 2,..., and nk for type k
 *   and (n1 + n2 +,...,+ nk = n) is:
 *   n! / (n1 ! n2 ! ,...,nk !)
 *   
 *   ex: If we want to assign 97 coders to 5 rooms (room 1-4 have 20 coders
 *   and room 5 have 17), we have 97!/(20!20!20!20!17!) ways to do it.
 * 
 * Combination:
 * Order doesn't matter.
 * 
 * No repetition:
 * n!/((n-k)!k!)
 * 
 * With repetition:
 * We choose k elements from an n-element set and each element can be 
 * chosen more than once.
 * f_k^n = (n+k-1)! / (k!(n-1)!)
 * 
 * ex: we have 11 identical balls and 3 different pockets, and we need to
 *     calculate the number o different divisions of these balls to the
 *     pockets.
 *     here: 3 is n, 11 is k
 * 
 * 		x1 + x2 +,...,+	xn = k, where xi >= 0.The number of solution
 * 		of this equation is f_k^n
 * 		Consider a vector (1,...,1) with n+k-1 1s
 * 		in which we want to change n-1 ones to 0s such that we can get n
 * 		groups of ones, each group represents a number.
 * 		(1,...,1,0,1,...,1,0,...,0,1,...,1)
 * 		   x1        x2              xn
 * 	
 * Derangement:
 * a permutation of the elements of a set such that none of the 
 * elements appear in their original position.
 * Number of Derangement of n elements: !n = [n!/e]
 * 
 * ex: There are 4 students A, B, C, D take a test and grade each other
 * 	   Surely no student should grade his own test.
 * 
 * @author hangou
 *
 */
public class Combinatorics {
	
	/**
	 * In LeetCode_day5
	 * Implement next permutation, which rearranges numbers 
	 * into the lexicographically next greater permutation of numbers.
	 * If such arrangement is not possible, 
	 * it must rearrange it as the lowest possible order (ie, sorted in ascending order).
	 * The replacement must be in-place, do not allocate extra memory.
	 * Here are some examples. Inputs are in the left-hand column and 
	 * its corresponding outputs are in the right-hand column.
	 * 1,2,3 → 1,3,2
	 * 3,2,1 → 1,2,3
	 * 1,1,5 → 1,5,1
	 * 
	 * Analysis:
	 * Assume, the next permutation in lexicographic ordering of A is B,
	 * where A = {a1,a2,a3,...,an} and B={b1,b2,b3,...bn}.
	 * 1. a1=b1, a2=b2,...,a_{k-1}=b_{k-1} and ak != bk
	 * 2. bk is the number min{aj | aj > ak ; j in {k+1,k+2,...,n}}
	 * 	  the smallest number which is behind ak in A and larger than ak
	 * 3. b_{k+1},...,bn is in ascending order
	 * 4. For any other permutations which are larger than A
	 *    the first element that different from A has the position which is equal or less than k 
	 *
	 * Algorithm:
	 * Step 1: Find the largest index k, such that A[k]<A[k+1]. 
	 *         If not exist, this is the last permutation. 
	 *         (in this problem just sort the vector and return.)
	 * Step 2: Find the largest index l, such that A[l]>A[k].
	 * Step 3: Swap A[k] and A[l].
	 * Step 4: Reverse A[k+1] to the end
	 *
	 */
	public static void nextPermutation(int[] a){
		int k = -1;
		for(int i = a.length - 1 ; i >= 1 ; i++)
			if(a[i] > a[i-1]) {
				k = i-1;
				break;
			}
		if(k == -1) return;
		int l = a.length-1;
		for(; l >= 0 ; ++l)
			if(a[l] > a[k]){
				break;
			}
		//swap a[l] and a[k]
		a[l] = a[l] ^ a[k];
		a[k] = a[l] ^ a[k];
		a[l] = a[l] ^ a[k];
		
		//reverse all elements from a[k+1]
		//another reversion can be done by stack or recursion
		//another way can be: 
		/*
		 * while(start < end){
		 * swap a[start] and a[end]
		 * start++, end--
		 * }
		 */
		int mid = (a.length + k + 1) / 2;
		for(int i = k+1 ; i <= mid ; i++){
			a[i] = a[i] ^ a[a.length-i+k];
			a[a.length-i+k] = a[i] ^ a[a.length-i+k];
			a[i] = a[i] ^ a[a.length-i+k];
		}
	}
	
	/**
	 * In LeetCode_day7 and LeetCode_day8
	 * Given a collection of numbers, return all possible permutations.
	 * No duplicates.
	 * 
	 * Analysis:
	 * Method 1:
	 * The basic idea is that swap two numbers of the array.
	 * For the length of n, the permutations can be generated by:
	 * 1) swap the 1st element with all the elements, including itself
	 * 2) Then the 1st element is fixed, go to next element
	 * 3) Until the last element is fixed.
	 * ex: a = {1,2,3}
	 * first i = 0:  {2,1,3},{3,2,1} // exchange 1 with all others
	 * then i = 1:   {1,2,3}->{1,3,2}
	 *               {2,1,3}->{2,3,1}
	 *               {3,2,1}->{3,1,2}
	 * then i = 2: stay
	 */
	public static void permutations(int[] a){
		List<int[]> res = new ArrayList<int[]>();
		res.add(a);
		for(int i = 0 ; i < a.length-1 ; i++){
			//i-1 element is fixed
			int cursize = res.size();
			for(int k = 0 ; k < cursize ; k++){//for all current permutation
				int[] t = res.get(k);
				for(int j = i+1 ; j < a.length ; j++){//exchange i and j where j > i
					int[] nt = Arrays.copyOf(t,t.length);
					nt[i] = nt[i] ^ nt[j];
					nt[j] = nt[i] ^ nt[j];
					nt[i] = nt[i] ^ nt[j];
					res.add(nt);
				}
			}
		}
		
		for(int i = 0 ; i < res.size() ; i++){
			System.out.println();
			for(int j : res.get(i))
				System.out.print(j+",");
		}
	}
	
	/**
	 * Method 2:
	 * one_permutations(a(n)) = insert n to permutation(a(n-1))
	 * This leads to subproblems.
	 * Find all permutations of a(n)<-
	 * 		Find all permutations of a(n-1) & insert n into them
	 * @param a
	 */
	public static void permutations1(int[] a){
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		List<Integer> t = new LinkedList<Integer>();
		res.add(t);
		for(int i = 0 ; i < a.length ; i++){//for every element
			int size = res.size();
			for(int j = 0 ; j < size ; j++){//for every half result
				t = res.get(j);
				for(int k = 1 ; k <= t.size() ; k++){//insert the element into the half result
					List<Integer> nt = new LinkedList<Integer>();
					nt.addAll(t);
					nt.add(k, a[i]);
					res.add(nt);
				}
				t.add(0,a[i]);
			}
		}
		
		for(int i = 0 ; i < res.size() ; i++){
			System.out.println();
			for(int j : res.get(i))
				System.out.print(j+",");
		}
	}
	
	/**
	 * In LeetCode_day8
	 * Given a collection of numbers that might contain duplicates, 
	 * return all possible unique permutations.
	 * 
	 * For example,
	 * [1,1,2] have the following unique permutations:
	 * [1,1,2], [1,2,1], and [2,1,1].
	 * 
	 * Method1:
	 * Just use next permutation mentioned above
	 * O(n lgn) for sorting
	 * O(n!/(n1!n2!,..,nk!) * n) for find all permutation
	 */
	public static void permutationsII(int[] a){
		Arrays.sort(a);
		List<int[]> res = new ArrayList<int[]>();
		res.add(a);
		while(true){
			int[] na = Arrays.copyOf(res.get(res.size()-1),res.get(res.size()-1).length) ;
			int k = -1;
			for(int i = na.length-1 ; i > 0 ; --i)
				if(na[i] > na[i-1]){
					k = i-1; break;
				}
			if(k == -1) break;
			int l = -1;
			for(int i = na.length-1 ; i >= 0 ; --i)
				if(na[i] > na[k]){
					l = i; break;
				}
			na[k] = na[k] ^ na[l];
			na[l] = na[k] ^ na[l];
			na[k] = na[k] ^ na[l];
			
			int start = k+1, end = na.length-1;
			while(start++ < end--){
				na[start] = na[start] ^ na[end];
				na[end] = na[start] ^ na[end];
				na[start] = na[start] ^ na[end];
			}
			res.add(na);
		}
		
		for(int i = 0 ; i < res.size() ; i++){
			System.out.println();
			for(int j : res.get(i))
				System.out.print(j+",");
		}
	}
	
	/**
	 * ！ Method 2:
	 * Just follow the swap method from permutations
	 * if there exist same element after current swap,
	 * there is no need to swap again. There are some subtree to be cut.
	 * But this needs certain order in the search tree
	 *                   122
	 *                 /     \    (swap first element)
	 *               212     221(X)
	 *                |       |  (swap second element)
	 *               221     212(X)
	 * @param a
	 */
	public static void permutationsII1(int[] a){
		List<int[]> res = new ArrayList<int[]>();
		res.add(a);
		for(int i = 0 ; i < a.length-1 ; i++){
			int size = res.size();
			for(int j = 0 ; j < size ; j++){
				int[] t = res.get(j);
				
				for(int k = i+1 ; k < a.length ; k++){
					int[] newa = Arrays.copyOf(t, t.length);
					newa[i] = newa[i] ^ newa[k];
					newa[k] = newa[i] ^ newa[k];
					newa[i] = newa[i] ^ newa[k];
					
					boolean flag = true;
					for(int m = i+1 ; m <= k ; ++m)
						if(newa[m] == newa[i]){//if exist duplicate after swap
							flag = false; break;
						}
					if(!flag) continue;//no need to swap
					res.add(newa);
				}
			}
		}
		for(int i = 0 ; i < res.size() ; i++){
			System.out.println();
			for(int j : res.get(i))
				System.out.print(j+",");
		}
	}
	
	/**
	 * ! In leetCode_day10
	 * The set [1,2,3,…,n] contains a total of n! unique permutations.
	 * By listing and labeling all of the permutations in order,
	 * We get the following sequence (ie, for n = 3):
	 * "123"
	 * "132"
	 * "213"
	 * "231"
	 * "312"
	 * "321"
	 * Given n and k, return the kth permutation sequence.
	 * Note: Given n will be between 1 and 9 inclusive.
	 */
	public static void permutationSequence(int n, int k){
	
	}
	
	public static void subset(){
		
	}
	
	public static void subsetII(){
		
	}
	
	public static void main(String[] args) {
		permutations(new int[]{1,2,3});
		System.out.println("**************");
		permutations1(new int[]{1,2,3});
		System.out.println("**************");
		permutationsII(new int[]{1,2,2});
		System.out.println("**************");
		permutationsII1(new int[]{1,2,2,2,3,3});
	}

}
